// 同余方程 乘法逆元 扩展欧几里得算法
// 测试链接 ：https://loj.ac/p/2605
// 相关帖子 ：https://www.cnblogs.com/dx123/p/16733758.html
// 相关帖子 ：https://oi-wiki.org/math/number-theory/linear-equation/
// 提交以下的code，可以直接通过

#include <bits/stdc++.h>

using namespace std;

#define ll long long

// 扩展欧几里得算法
int exgcd(int a, int b, int& x, int& y)
{
    if(b == 0)
    {
        x = 1;
        y = 0;
        return a;
    }
    int x1, y1, d;
    d = exgcd(b, a % b, x1, y1);
    x = y1, y = x1 - a / b * y1;
    return d;
}

// ax ≡ b (mod m)
// 返回最小正整数解 x
ll compute(int a, int b, int m)
{
    int x, y;
    int d = exgcd(a, m, x, y);
    return (1LL * x * b / d % m + m) % m;
}

int main()
{
    int a, b = 1, m, x;
    scanf("%d%d", &a, &m);
    printf("%lld\n", compute(a, b, m));

    return 0;
}